package org.apache.commons.graph.view.iterator

import com.gitee.wsl.collections.deque.ArrayDeque
import com.gitee.wsl.func.consumer.Consumer
import kotlinx.atomicfu.AtomicInt
import kotlinx.atomicfu.atomic
import org.apache.commons.graph.view.ITargetVertexView
import org.apache.commons.graph.visitor.ITargetVertexVisitor
import kotlin.jvm.JvmOverloads

/**
 * Iterates over the edges of a graph in topological order.
 *
 * @param <V> Vertex type
</V> */
class TopologicalOrderIterator<V>(
    vertexSet: Collection<V>,
    private val graph: ITargetVertexVisitor<V>,
    allowLoop: Boolean,
) : Iterator<V> {
    private val countMap = LinkedHashMap<V, AtomicInt>()
    private val empties = ArrayDeque<V>()
    private val allowLoop: Boolean

    init {
        populate(vertexSet, countMap, empties)
        this.allowLoop = allowLoop
    }

    @JvmOverloads
    constructor(graph: ITargetVertexView<V>, allowLoop: Boolean = true) : this(graph.vertexSet(), graph, allowLoop)

    private fun populate(vertexSet: Collection<V>, countMap: MutableMap<V, AtomicInt>, empties: ArrayDeque<V>) {
        for (v in vertexSet) {
            countMap[v] = atomic(0)
        }

        for (v in vertexSet) {
            graph.forEachTarget(v, Consumer { target: V ->
                val ints = countMap[target]
                ints?.incrementAndGet()
            })
        }

        for (entry in countMap.entries) {
            if (entry.value.value == 0) {
                empties.add(entry.key)
            }
        }
        countMap.keys.removeAll(empties)
    }

    override fun hasNext(): Boolean {
        return !empties.isEmpty() || (allowLoop && breakLoop())
    }

    override fun next(): V {
        do {
            val v = nextNoCycle()
            if (v != null) return v

            if (!allowLoop)  throw IllegalStateException()

            if (!breakLoop()) throw IllegalStateException()
        } while (true)
    }

    fun breakLoop(): Boolean {
        if (countMap.isEmpty()) return false

        val it = countMap.keys.iterator()
        val target = it.next()
        it.remove()
        empties.addLast(target)
        return true
    }

    fun nextNoCycle(): V {
        val v = empties.removeFirst()
        graph.forEachTarget(v, Consumer { target: V ->
            val ints = countMap.get(target)
            if (ints != null) {
                if (ints.decrementAndGet() == 0) {
                    countMap.remove(target)
                    empties.addLast(target)
                }
            }
        })
        return v
    }

    val remaining: Set<V>
        get() = countMap.keys

    fun containsCycle(): Boolean {
        while (hasNext()) {
            nextNoCycle()
        }
        return !countMap.isEmpty()
    }

    fun findCycles(): Set<V> {
        while (hasNext()) {
            nextNoCycle()
        }

        return countMap.keys
    }

    fun findOneCycle(): List<V> {
        val visited = ArrayList<V>()
        for (node in countMap.keys) {
            visited.clear()
            if (containsCycle(node, visited)) break
        }
        return visited
    }

    fun displayOneCycle(): String {
        var cycle: List<V> = findOneCycle()
        cycle = cycle.reversed()
        return cycle.joinToString( "->")
    }

    private fun containsCycle(node: V, visited: MutableList<V>): Boolean {
        val index = visited.indexOf(node)
        if (index >= 0) {
            // 仅保留最小化的部分
            for (i in 0..<index) {
                visited.removeAt(0)
            }
            visited.add(node)
            return true
        }
        visited.add(node)
        for (target in graph.getTargetVertexes(node)) {
            if (containsCycle(target, visited)) return true
        }
        visited.removeAt(visited.size - 1)
        return false
    }
}